package twoPointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class numSum {
    public static void main(String[] args) {
        int[] a={1,3,6,8,9};
        System.out.println(Arrays.toString(twoSum(a, 7)));
    }

    public static int[] twoSum(int[] nums, int target){
        if (nums == null ||nums.length==0) {
            return null;
        }
        int[] result={-1,-1};
        int start=0;
        int end=nums.length-1;
        while(start<end){
            if (nums[start]+nums[end]<target){
                start++;
            }else if(nums[start]+nums[end]>target){
                end--;
            }else{
                result[0]=start+1;
                result[1]=end+1;
                break;
            }
        }
        return result;
    }
    
    public static  List<List<Integer>> threeSum(int[] numbers){
        if (numbers == null ||numbers.length==0) {
            return null;
        }
        List<List<Integer>> result=new ArrayList<>();
        Arrays.sort(numbers);
        int len =numbers.length;
        for (int i = 0; i < len-2; i++) {
            if (i>0 && numbers[i]==numbers[i-1]){
                continue;
            }
            int left=i+1;
            int right=len-1;
            while (left<right){
                if (numbers[i]+numbers[left]+numbers[right]==0){
                    List<Integer> list=new ArrayList<>();
                    list.add(numbers[i]);
                    list.add(numbers[left]);
                    list.add(numbers[right]);
                    left++;
                    right--;
                    result.add(list);
                    while(left<right && numbers[left]==numbers[left-1]){
                        left++;
                    }
                    while(left<right && numbers[right]==numbers[right+1]){
                        right--;
                    }
                } else if (numbers[i]+numbers[left]+numbers[right]>0) {
                    right--;
                }else{
                    left++;
                }
            }
        }
        return  result;
    }
}
